package bintree.my_bin_tree;

import java.util.NoSuchElementException;

/**
 * 基础的BST实现
 * 不包含重复元素
 * @author yuisama
 * @date 2021/12/14 16:27
 **/
public class BinarySearchTree<E extends Comparable<E>> {
    // 节点类定义
    private class Node {
        private E val;
        private Node left;
        private Node right;

        public Node(E val) {
            this.val = val;
        }
    }
    private int size;
    // 根节点
    private Node root;

    public int getSize() {
        return size;
    }

    public void add(E newVal) {
        root = add(root,newVal);
    }

    /**
     * 向以root为根节点的BST中插入新元素,返回插入后的树根
     * @param root
     * @param newVal
     * @return 插入后的根节点
     */
    private Node add(Node root, E newVal) {
        if (root == null) {
            root = new Node(newVal);
            size ++;
        }
        if (newVal.compareTo(root.val) < 0) {
            // 左树插入
            root.left = add(root.left,newVal);
        }else if (newVal.compareTo(root.val) > 0){
            // 右数插入
            root.right = add(root.right,newVal);
        }
        return root;
    }

    public boolean contains(E val) {
        return contains(root,val);
    }

    /**
     * 删除BST中值为e的节点
     * @param e
     */
    public void remove(E e) {
        root = remove(root,e);
    }

    /**
     * Hibbard Deletion
     * 在以root为根节点的BST中删除值为e的节点，返回删除后的树根
     * @param root
     * @param e
     * @return
     */
    private Node remove(Node root, E e) {
        if (root == null) {
            return null;
        }
        if (e.compareTo(root.val) < 0) {
            // 左树删除
            root.left = remove(root.left,e);
            return root;
        }else if (e.compareTo(root.val) > 0) {
            // 右树删除
            root.right = remove(root.right,e);
            return root;
        }else {
            // 当前节点就是待删除节点
            if (root.left == null) {
                // 只有右树，返回右树树根
                Node right = root.right;
                root.right = null;
                size --;
                return right;
            }
            if (root.right == null) {
                // 只有左树，返回左树树根
                Node left = root.left;
                root.left = null;
                size --;
                return left;
            }
            // 此时左右树都不为空，找到当前root的后继作为新的树根
            Node successor = minimum(root.right);
            // 在右树中删除该节点
            successor.right = removeMin(root.right);
            successor.left = root.left;
            root.left = root.right = null;
            // 此处size不用--，因为在removeMin中已经删除了successor，size--了。
            return successor;
        }
    }

    /**
     * 判断以root为根节点的树中是否包含元素val
     * @param root
     * @param val
     * @return
     */
    private boolean contains(Node root, E val) {
        if (root == null) {
            return false;
        }
        if (root.val.equals(val)) {
            return true;
        }else if (val.compareTo(root.val) < 0) {
            return contains(root.left,val);
        }else {
            return contains(root.right,val);
        }
    }

    public E minimum() {
        if (isEmpty()) {
            throw new NoSuchElementException("BST is empty!");
        }
        return minimum(root).val;
    }

    public E removeMin() {
        E ret = minimum();
        root = removeMin(root);
        return ret;
    }

    /**
     * 删除以root为根节点的BST的最小值节点
     * @param root 当前BST的根
     * @return 删除最小值节点的树根
     */
    private Node removeMin(Node root) {
        if (root.left == null) {
            Node right = root.right;
            root.right = null;
            size --;
            return right;
        }
        root.left = removeMin(root.left);
        return root;
    }

    public E removeMax() {
        E ret = maximum();
        root = removeMax(root);
        return ret;
    }

    /**
     * 删除以root为根节点的BST的最大值节点
     * @param root 当前BST的根
     * @return 删除最大值节点的树根
     */
    private Node removeMax(Node root) {
        if (root.right == null) {
            Node left = root.left;
            root.left = null;
            size --;
            return left;
        }
        root.right = removeMax(root.right);
        return root;
    }

    /**
     * 找到以root为根的二叉树最小值节点
     * @param root
     * @return 最小值节点
     */
    private Node minimum(Node root) {
        if (root.left == null) {
            return root;
        }
        return minimum(root.left);
    }

    public E maximum() {
        if (isEmpty()) {
            throw new NoSuchElementException("BST is empty!");
        }
        return maximum(root).val;
    }

    /**
     * 找到以root为根的二叉树最大值节点
     * @param root
     * @return 最大值节点
     */
    private Node maximum(Node root) {
        if (root.right == null) {
            return root;
        }
        return maximum(root.right);
    }

    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBSTString(root,0,sb);
        return sb.toString();
    }

    /**
     * 先序遍历以当前root为根节点的BST字符串
     * @param root
     * @param depth
     * @param sb
     */
    private void generateBSTString(Node root, int depth, StringBuilder sb) {
        if (root == null) {
            sb.append(generateDepthString(depth)).append("NULL\n");
            return;
        }
        sb.append(generateDepthString(depth)).append(root.val).append("\n");
        generateBSTString(root.left,depth + 1,sb);
        generateBSTString(root.right,depth + 1,sb);
    }

    /**
     * 按深度打印--
     * 每向下一层多两个-
     * @param depth
     * @return
     */
    private String generateDepthString(int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
}